package threshold;



class ListNodes{
    int val;
    ListNodes next;
    ListNodes(){}
    ListNodes(int val){this.val = val;}
    ListNodes(int val, ListNodes next) { this.val = val; this.next=next; }

}

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-02 18:26
 * @Version 1.0
 */
public class MergeTwoLists {

    /**
     * 不带头结点的单链表合并的时候用指针p和q分别指向两个表的表头将表头元素较小的那个表，同时list表也赋值一个尾指针
     * @param list1
     * @param list2
     * @return
     */
    public ListNodes mergeTwoLists(ListNodes list1, ListNodes list2) {
        if(list1==null || list2==null){
            return list1!=null?list1:list2;
        }
        if(list1==null && list2==null){return null;}

        ListNodes p=list1,q=list2,list,r;
        if(list1.val<=list2.val){
            list = list1;
            r = list;
            p = p.next;
        }else{
            list = list2;
            r = list;
            q = q.next;
        }

        while(p!=null && q!=null){
            if(p.val<=q.val){
                r.next = p;
                r = p;
                p = p.next;
            }else{
                r.next = q;
                r =q;
                q=q.next;
            }
        }

        r.next = p!=null?p:q;
        return list;
    }


    public ListNodes merge(ListNodes ls1,ListNodes ls2){
        ListNodes p=ls1.next,q=ls2.next,list,r;
        if(p.val<=q.val){
            list = ls1;
            list.next = p;
            r=p;
            p=p.next;
        }else {
            list = ls2;
            list.next=q;
            r=q;
            q=q.next;
        }

        while(p!=null &&q!=null){
            if(p.val<=q.val){
                r.next=p;
                r=p;
                p=p.next;
            }else{
                r.next=q;
                r=q;
                q=q.next;
            }
        }

        r.next = p!=null?p:q;
        return list;
    }
    public static void main(String[] args) {
        MergeTwoLists mergeTwoLists = new MergeTwoLists();
        ListNodes listNodes,p;

        ListNodes lsA= new ListNodes();
        ListNodes ls1= new ListNodes(1);
        ListNodes ls2 = new ListNodes(2);
        ListNodes ls3 = new ListNodes(4);
        lsA.next=ls1; ls1.next = ls2; ls2.next = ls3;

        ListNodes lsB= new ListNodes();
        ListNodes ls4= new ListNodes(1);
        ListNodes ls5 = new ListNodes(3);
        ListNodes ls6 = new ListNodes(4);
        lsB.next=ls4; ls4.next = ls5; ls5.next = ls6;

        listNodes = mergeTwoLists.merge(lsA,lsB);
        p = listNodes.next;
        while(p!=null){
            System.out.println(p.val);
            p=p.next;
        }
    }
}
